# Definition for a binary tree node.
"""
二叉树:
满二叉树
完全二叉树
二叉搜索树
平衡二叉搜索树

"""


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def inorderTraversal(self, root: TreeNode):
        result = []
        stack = []
        current = root

        while current or stack:
            # 遍历左子树，将节点压入栈
            while current:
                stack.append(current)
                current = current.left

            # 弹出栈顶节点（访问该节点）
            current = stack.pop() 
            result.append(current.val)

            # 移动到右子节点
            current = current.right

        return result

    def second_inorderTraversal(self, root: TreeNode):
        result = []

        def inorder(node):
            if not node:
                return

            # 遍历左子树
            inorder(node.left)

            # 访问根节点
            result.append(node.val)

            # 遍历右子树
            inorder(node.right)

        inorder(root)
        return result


if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right = TreeNode(3)
    s = Solution()
    print(s.second_inorderTraversal(root))